/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) 
    {
        map<Node*,Node*> copyMap;
        Node* copytail=nullptr,*copyhead=nullptr;
        Node* cur=head;
        //将原链表的拷贝一份，注意这里只处理了next，没处理random
        while(cur)
        {
            if(copytail==nullptr)
            {
                copyhead=copytail=new Node(cur->val);
            }
            else
            {
                copytail->next=new Node(cur->val);
                copytail=copytail->next;
            }

            //kv储存，k代表原链表节点，v代表拷贝后的链表节点
            copyMap[cur]=copytail;
            cur=cur->next;           
        }

        //next处理完毕，接下来处理random
        Node* copy=copyhead;
        cur=head;
        while(cur)
        {
            if(cur->random==nullptr)
            {
                copy->random=nullptr;
            }
            else
            {
                copy->random=copyMap[cur->random];
            }
            cur=cur->next;
            copy=copy->next;
        }
        return copyhead;
    }
};